package com.njupt.DynamicProgramming;

/**
 * @Author: wujiaming
 * @CreateTime: 2025/2/8 9:46
 * @Description: 518. 零钱兑换 II
 *
 * 1、dp数组的含义，凑成容量为j的面额（背包） 有dp[j]种方法
 * 2、递推公式 dp[j] += dp[j-coins[i]]
 * 3、dp数组初始化
 * @Version: 1.0
 */


public class Change_518 {

    public int change(int amount, int[] coins) {
        int[] dp = new int[amount+1];
        dp[0] =1;
        for (int i = 0; i < coins.length; i++) {
            for (int j = coins[i]; j <=amount ; j++) {
                dp[j] += dp[j-coins[i]];
            }
        }
        return dp[amount];
    }

    public static void main(String[] args) {
        Change_518 test = new Change_518();
//        int[] coins = {1, 2, 5};
        int[] coins = {10};
        System.out.println(test.change(10, coins));
    }
}
